package _11_整理题目._2_二叉树_递归_dfs_bfs._递归;

import org.junit.Test;
import util.TreeNode;

/**
 * https://leetcode-cn.com/problems/symmetric-tree/
 *
 * 给定一棵二叉树，判断其是否是自身的镜像（即：是否关于中间的线轴对称）
 * 
 * 递归三步曲：
 *      1、确定 递归函数的输入参数 和 返回值
 *      2、确定 递归终止条件
 *      3、编写 递归逻辑
 * 
 * 首先搞懂，判断的相当于是 根节点 的左右子树的每个下属节点是否都相等，
 * 所以相当于要判断两个子树，所以 输入参数是 两个 TreeNode, 返回值是 boolean
 * 
 * 递归终止条件是比较两个 TreeNode 是否相等，
 * 可以分为几种情况：
 *      left, right 都为 null， 返回 true
 *      left, right 有只一个为 null，返回 false
 *      left, right 都不为 null，比较它们的 val 是否相等，递归比较 左右子树
 *      
 * 通过了递归终止条件，说明 left == right,
 * 接下来要递归左子树和右子树 是否 为true
 * 返回 左右子树的 判断结果 &&
 * 
 */
public class _01_判断二叉树是否对称 {
    
    public boolean isSymmetric (TreeNode root) {
        return recursion(root.left, root.right);
    }
    
    private boolean recursion(TreeNode r1, TreeNode r2) {
        if (r1==null && r2==null) return true;

        if (r1==null || r2==null) {
            return false;
        } else {
            return r1.val==r2.val && recursion(r1.left, r2.right) && recursion(r1.right, r2.left);
        }
    }
    
    @Test
    public void main() {
        Integer[] input = {1, 2, 2, 3, 4, 4, 3};
        TreeNode root = TreeNode.getTreeFromArray(input);
        System.out.println(isSymmetric(root));
    }
}
